public class Solution {
    class ListNode{
        int val;
        ListNode next;

        public ListNode() {
        }
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode ans = new ListNode();
        ListNode tail = ans;
        if(list1 == null && list2 == null)
            return null;

        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                tail.next = list1;
                tail = tail.next;
                list1 = list1.next;
            }else{
                tail.next = list2;
                tail = tail.next;
                list2 = list2.next;
            }
        }

        if(list1 == null && list2 != null){
            tail.next = list2;
        }
        if(list1 != null && list2 == null){
            tail.next = list1;
        }
        return ans.next;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0;
        int lenB = 0;
        int tmp = 0;
        ListNode L = headA;
        ListNode S = headB;
        while(L != null){
            lenA++;
        }

        while(S != null){
            lenA++;
        }

        L = headA;
        S = headB;
        tmp = lenA - lenB;

        if(lenA - lenB < 0){
            L = headB;
            S = headA;
            tmp = lenB - lenA;
        }

        for(int i = 0; i < tmp; i++){
            L = L.next;
        }

        while(L != null && S != null){
            if(L == S){
                return L;
            }
            L = L.next;
            S = S.next;
        }
        return null;
    }

    public boolean chkPalindrome(ListNode A) {
       ListNode fast = A;
       ListNode slow = A;

       while(fast != null && fast.next != null){
           fast = fast.next.next;
           slow = slow.next;
       }

       ListNode cur = slow;
       ListNode prev = null;
       ListNode head = slow;
       while(cur != null){
           cur = cur.next;
           head.next = prev;
           prev = head;
           head = cur;
       }

       ListNode tmp = prev;

       while(tmp != null){
           if(tmp.val != A.val){
               return false;
           }
           tmp = tmp.next;
           A = A.next;
       }

       return true;
    }
}
